/**
 * 
 * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，
最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 */
/**
 * 
 *    6
 *  2   8
 * 0 4 7 9
 *  3 5
 */
 /**
  * 
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。
  */
/**
 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
 */

let root = [6,2,8,0,4,7,9,null,null,3,5]
let p = 2
let q = 8


lowestCommonAncestor(root, p, q)

function lowestCommonAncestor(root, p, q){
    //先梳理出二叉树的层级
    /**
     * 1级 1个元素  2的0次幂
     * 2级 2个元素  2的1次幂
     * 3级 4个元素  2的2次幂
     * 4级 8个元素  2的3次幂
     * n级 2的（n-1）次幂个元素
     */
    
    let bt = binaryTree(root, p , q)
    let parr = bt[0]
    let qarr = bt[1]
    let samePar = []
    // console.log(bt)
    for(let i in parr){
        for(let j in qarr){
            if(parr[i] === qarr[j]){
                samePar.push(parr[i])
            }
        }
    }
    console.log(samePar)

}
// binaryTree(root, p , q)
function binaryTree(arr, p, q){
    let obj = {}
    for(let i = 1; i <= arr.length; i++){
        let lvarr = []
        let lvnum = Math.pow(2, i-1)
        
        for(let j = 0; j < lvnum; j++){
            lvarr.push(arr[j])
        }
        obj[i] = lvarr
        arr.splice(0, lvnum)
    }
    // console.log(obj)
    let pmsg = findLv(obj, p)
    let qmsg = findLv(obj, q)

    // console.log(pmsg, qmsg)
    let pPar = findParents(pmsg, obj)
    let qPar = findParents(qmsg, obj)
    // console.log(pPar, qPar)
    return [pPar, qPar]
}

function findLv(obj, tag){
    //找到元素的祖先
    //先找到元素的层级
    for(let i in obj){
        let flag = obj[i].indexOf(tag)
        // console.log(i, flag)
        if(flag !== -1){
            return [parseInt(i), flag]
        }
    }
}

function findParents(msg, obj){
    let parentsArr = []
    let lv = msg[0]
    let flag = msg[1]

    for(let i = lv; i > 1; i--){
        let arr = obj[i - 1]
        let parFlag = Math.floor(flag/2)    //向下取整
        // console.log(parFlag)
        parentsArr.push(arr[parFlag])
        flag = parFlag + 1
    }
    // console.log(parentsArr)
    return parentsArr
}
